//第二种方法：
class Solution {
public:
    ListNode* mergelistsort(ListNode* begin1,ListNode* begin2)
    {
        ListNode* newhead = new ListNode();
        ListNode* ret = newhead;
        ListNode* cur = newhead;
        while(begin1&&begin2)
        {
            if(begin1->val<begin2->val)
            {
                cur->next = begin1;
                begin1 = begin1->next;
                cur = cur->next;
            }
            else
            {
                cur->next = begin2;
                cur = cur->next;
                begin2 = begin2->next;
            }
        }
        cur->next = begin1?begin1:begin2;//再将剩下的部分也放入到cur中
        return newhead->next;//返回这个排序好的新链表
    }
    ListNode* mergelist(vector<ListNode*>& lists,int begin,int end)
    {
        //begin和end分别代表的是当前这个递归函数要处理的链表的个数,当end-begin等于1的时候代表
        //现在的begin和end分别指向两个相邻的链表
        int mid = end - begin;
        if(mid == 0)
        {
            return nullptr;
        }
        if(mid == 1)
        {
            return lists[begin];
        }
        //再去分治左半部分
        auto left = mergelist(lists,begin,begin+mid/2);
        auto right = mergelist(lists,begin+mid/2,end);//递归右半部分
        //现在左半部分和右半部分已经是有序的单独链表了，再将这两个链表进行合并
        return mergelistsort(left,right);
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //第二种方法：将vector中的链表进行分治，最后就能够将链表中的链表分成单独单独一串一串的链表
        //然后再按照两两合并的方式将链表进行合并
        return mergelist(lists,0,lists.size());//我要完成list中所有链表的排序并且最后会返回一个新的头节点
    }
};
//第一种方法使用最小堆
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //第一种方法使用最小堆，首先将所有链表的头节点都放入到堆中，然后将堆顶的元素拿出来放入到
        //新建立的链表中，如果这个被拿出来的链表的next节点不为空，就将next节点也放入到堆中
        // 使用最小堆
        auto cmp = [](ListNode* a1, ListNode* a2) {
            return a1->val > a2->val; // 小堆，较小的值优先
        };
        priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)> que;
        int n = lists.size();
         // 将所有不为空的头节点放入堆中
        for (ListNode* list : lists) {
            if (list != nullptr) {
                que.push(list);
            }
        }

        ListNode* newhead = new ListNode(0); // 哨兵节点
        ListNode* cur = newhead;

        // 处理堆中的节点
        while (!que.empty()) {
            ListNode* p = que.top(); // 取出堆顶元素
            que.pop();

            cur->next = p; // 连接到新链表
            cur = cur->next;

            // 如果当前节点的 next 不为空，将 next 放入堆中
            if (p->next != nullptr) {
                que.push(p->next);
            }
        }

        return newhead->next; // 返回合并后的链表
    }
};